#include "headfiles.h"
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

#define MAX_INF 1.0e8f

Graph::Graph() {
	head = NULL;
	node_list = NULL;
	node_num = 0;
	dist_matrix = NULL;
}

Graph::~Graph() {
	int i;
	for (i = 0; i < node_num; i++) {
		NEIGHBOR *tmp;
		NEIGHBOR *neighbor = node_list[i]->neighbor;
		while (neighbor) {
			tmp = neighbor;
			neighbor = neighbor->next;
			free(tmp);
		}

		free(node_list[i]);
	}
	free(node_list);

	free(dist_matrix);
}

bool Graph::create(const char *file_name) {
	if (file_name == NULL) {
		cout << "Input file name is NULL!" << endl;
		return false;
	}

	fstream nf;
	nf.open(file_name, fstream::in);
	if (!nf.is_open()) {
		cout << "Open file " << file_name << " error!" << endl;
		return false;
	}

	string str;
	// Retrieve the number of nodes of the graph
	nf >> str;
	if (str.empty()) {
		cout << "Empty input file!" << endl;
		return false;
	}

	node_num = atoi(str.c_str());
	if (node_num <= 0) {
		cout << "Error node number " << node_num << endl;
		return false;
	}

	node_list = (NODE **)malloc(sizeof(NODE *) * node_num);
	if (node_list == NULL) {
		cout << "Allocate node pointer buffer error!" << endl;
		return false;
	}

	int i;
	for (i = 0; i < node_num; i++) {
		node_list[i] = (NODE *)malloc(sizeof(NODE));
		if (node_list[i] == NULL) {
			cout << "Allocate node " << i << " error, NULL!" << endl;
			return false;
		}
		memset(node_list[i], 0, sizeof(NODE));
		node_list[i]->id = i + 1;
	}

	// head points to the first node
	head = node_list[0];

	// Allocate buffer to store the matrix
	dist_matrix = (float *)malloc(node_num * node_num * sizeof(float));
	if (dist_matrix == NULL) {
		cout << "Allocate matrix buffer error, NULL!" << endl;
		return false;
	}

	// retrive the distance matrix
	int index = 0;
	while (nf >> str) {
		if (str.empty()) {
			break;
		}

		float val = atof(str.c_str());
		if (val < 0.0f) {
			val = MAX_INF;
		}
		dist_matrix[index++] = val;
	}

	if (index != node_num * node_num) {
		cout << "distance matrix is incorrect" << endl;
		return false;
	}

	// construct the graph
	construct();
	
	return true;	
}

bool Graph::construct() {
	int i, j;
	NEIGHBOR *last_neighbor = NULL;
	NEIGHBOR *neighbor;

	// each node checks its corresponding row
	for (i = 0; i < node_num; i++) {
		last_neighbor = NULL;
		for (j = 0; j < node_num; j++) {
			if (j != i) {
				int loc = i * node_num + j;
				if (dist_matrix[loc] < MAX_INF) {
					neighbor = (NEIGHBOR *)malloc(sizeof(NEIGHBOR));
					if (neighbor == NULL) {
						cout << "Allocate labor error, NULL!" << endl;
						return false;
					}

					neighbor->next = NULL;
					neighbor->dist = dist_matrix[loc];
					neighbor->node = node_list[j];
					if (last_neighbor == NULL) {
						node_list[i]->neighbor = neighbor;
					}
					else {
						last_neighbor->next = neighbor;
					}

					last_neighbor = neighbor;
				}
			}
		}
	}

	return true;
}

bool Graph::resetVisitCount() {
	int i;
	for (i = 0; i < node_num; i++) {
		node_list[i]->visit_count = 0;
	}

	return true;
}

bool Graph::breathFirstSearch() {
	queue<NODE *> node_queue;
	NODE *node;
	NEIGHBOR *neighbor;

	resetVisitCount();

	node_queue.push(head);
	while (!node_queue.empty()) {
		node = node_queue.front();
		node_queue.pop();
		if (node != NULL) {
			// The node is not visisted yet
			if (node->visit_count == 0) {
				cout << "node id = " << node->id << endl;

				// indicate the node is visit_count
				node->visit_count = 1;

				// check its neighbors
				neighbor = node->neighbor;
				while (neighbor) {
					node = neighbor->node;
					// If the neighbor is not visit_count yet
					if (node->visit_count == 0) {
						node_queue.push(node);
					}
					neighbor = neighbor->next;
				}
			}
		}
	}

	return true;
}

bool Graph::deepFirstSearch() {
	stack<NODE *> node_stack;
	NODE *node;
	NEIGHBOR *neighbor;
	int i;
	
	resetVisitCount();

	node_stack.push(head);
	while (!node_stack.empty()) {
		node = node_stack.top();

		if (node->visit_count == 0) {
			cout << "node id = " << node->id << endl;
		}
		node->visit_count++;

		neighbor = node->neighbor;
		for (i = 1; i < node->visit_count; i++) {
			if (neighbor != NULL) {
				neighbor = neighbor->next;
			}
			else {
				break;
			}
		}

		if (neighbor != NULL) {
			node_stack.push(neighbor->node);
		}
		else {
			node_stack.pop();
		}
	}	


	return true;
}

static bool DeepFirstSearchRecursive(NODE *head) {
	if (head == NULL) {
		return true;
	}

	cout << "node id = " << head->id << endl;
	head->visit_count = 1;

	NEIGHBOR *neighbor = head->neighbor;
	while (neighbor) {
		if (neighbor->node->visit_count == 0) {
			DeepFirstSearchRecursive(neighbor->node);
		}
		neighbor = neighbor->next;
	}

	return true;
}

bool Graph::deepFirstSearchRecur() {

	resetVisitCount();

	return DeepFirstSearchRecursive(head);
}

int Graph::getMinDistNode(vector<NODE *> &node_vec, 
						  float *min_dist) {
	float dist = MAX_INF;
	int i, min_index = -1;

	for (i = 0; i < node_num; i++) {
		if (node_vec[i]->visit_count == 0) {
			if (min_dist[i] < dist) {
				dist = min_dist[i];
				min_index = i;
			}
		}
	}

	if (min_index != -1) {
		node_vec[min_index]->visit_count = 1;
	}

	return min_index;
}

bool Graph::shortestPath(int src_index) {
	vector<NODE *> node_vec;
	NODE **prev_nodes = (NODE **) malloc(sizeof(NODE *) * node_num);
	if (prev_nodes == NULL) {
		cout << "Allocate all nodes pointer error, NULL!" << endl;
		return false;
	}
	memset(prev_nodes, 0, sizeof(NODE *) * node_num);

	float *dist = (float *)malloc(sizeof(float) * node_num);
	if (dist == NULL) {
		cout << "Allocate dist matrix error, NULL!" << endl;
		return false;
	}
	memset(dist, 0, sizeof(float) * node_num);

	int i;
	for (i = 0; i < node_num; i++) {
		int loc = src_index * node_num + i;
		dist[i] = dist_matrix[loc];
		prev_nodes[i] = NULL;
		node_list[i]->visit_count = 0;
		node_vec.push_back(node_list[i]);
	}
	node_list[src_index]->visit_count = 1;
	
	NODE *node;
	int min_index = getMinDistNode(node_vec, dist);
	while (min_index != -1) {
		float min_dist = dist[min_index];
		node = node_list[min_index];

		// check all its neighbors
		NEIGHBOR *neighbor = node->neighbor;
		while (neighbor) {
			int index = neighbor->node->id - 1;
			if (dist[index] > min_dist + neighbor->dist) {
				dist[index] = min_dist + neighbor->dist;
				prev_nodes[index] = node;
			}
			neighbor = neighbor->next;
		}

		min_index = getMinDistNode(node_vec, dist);
	}

	cout << "Minimum dist to source is:" << endl;
	for (i = 0; i < node_num; i++) {
		cout << "Node " << i + 1 << ", distance to source is: " << dist[i] << endl;
		cout << "Path to source: ";
		node = prev_nodes[i];
		while (node) {
			cout << node->id << "\t";
			node = prev_nodes[node->id - 1];
		}
		cout << endl;
	}

	free(prev_nodes);
	free(dist);

	return true;
}

// This function is to print out the dist marix
bool Graph::print() {
	if (dist_matrix == NULL) {
		cout << "Distance matrix is NULL!" << endl;
		return false;
	}

	int i, j;
	cout << "Dist matrix is:" << endl;
	for (i = 0; i < node_num; i++) {
		for (j = 0; j < node_num; j++) {
			int loc = i * node_num + j;
			cout << dist_matrix[loc] << "\t";
		}
		cout << endl;
	}

	return true;
}


